{
 "cells": [
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### Title: #Number of Single Divisor Triplets"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Difficulty: #Medium"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Category Title: #Algorithms"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Tag Slug: #math"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Name Translated: #数学"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Solution Name: singleDivisorTriplet"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Translated Title: #单因数三元组"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Translated Content:\n",
    "<p>给定一个下标从 <strong>0</strong> 开始的正整数数组 <code>nums</code>。由三个&nbsp;<strong>不同&nbsp;</strong>索引&nbsp;<code>(i, j, k)</code> 组成的三元组，如果 <code>nums[i] + nums[j] + nums[k]</code> 能被 <code>nums[i]</code>、<code>nums[j]</code>&nbsp;或 <code>nums[k]</code> 中的&nbsp;<strong>一个&nbsp;</strong>整除，则称为 <code>nums</code> 的&nbsp;<strong>单因数三元组</strong>。</p>\n",
    "\n",
    "<p>返回 <em><code>nums</code> 的单因数三元组</em>。</p>\n",
    "\n",
    "<p>&nbsp;</p>\n",
    "\n",
    "<p><strong>示例 1:</strong></p>\n",
    "\n",
    "<pre>\n",
    "<strong>输入:</strong> nums = [4,6,7,3,2]\n",
    "<strong>输出:</strong> 12\n",
    "<strong>解释:\n",
    "</strong>三元组索引 (0, 3, 4), (0, 4, 3), (3, 0, 4), (3, 4, 0), (4, 0, 3), 和 (4, 3, 0) 的值为 [4, 3, 2] (或者说排列为 [4, 3, 2]).\n",
    "4 + 3 + 2 = 9 只能被 3 整除，所以所有的三元组都是单因数三元组。\n",
    "三元组索引 (0, 2, 3), (0, 3, 2), (2, 0, 3), (2, 3, 0), (3, 0, 2), 和 (3, 2, 0) 的值为 [4, 7, 3]  (或者说排列为 [4, 7, 3]).\n",
    "4 + 7 + 3 = 14 只能被 7 整除，所以所有的三元组都是单因数三元组。\n",
    "一共有 12 个单因数三元组。\n",
    "</pre>\n",
    "\n",
    "<p><strong>示例 2:</strong></p>\n",
    "\n",
    "<pre>\n",
    "<strong>输入:</strong> nums = [1,2,2]\n",
    "<strong>输出:</strong> 6\n",
    "<strong>提示:</strong>\n",
    "三元组索引 (0, 1, 2), (0, 2, 1), (1, 0, 2), (1, 2, 0), (2, 0, 1), 和 (2, 1, 0) 的值为 [1, 2, 2] (或者说排列为 [1, 2, 2]).\n",
    "1 + 2 + 2 = 5 只能被 1 整除，所以所有的三元组都是单因数三元组。\n",
    "一共有6个单因数三元组。</pre>\n",
    "\n",
    "<p><strong>示例 3:</strong></p>\n",
    "\n",
    "<pre>\n",
    "<strong>输入:</strong> nums = [1,1,1]\n",
    "<strong>输出:</strong> 0\n",
    "<strong>提示:</strong>\n",
    "没有单因数三元组。\n",
    "注意 (0, 1, 2) 不是单因数三元组。 因为 nums[0] + nums[1] + nums[2] = 3，3 可以被 nums[0], nums[1], nums[2] 整除。\n",
    "</pre>\n",
    "\n",
    "<p>&nbsp;</p>\n",
    "\n",
    "<p><strong>提示:</strong></p>\n",
    "\n",
    "<ul>\n",
    "\t<li><code>3 &lt;= nums.length &lt;= 10<sup>5</sup></code></li>\n",
    "\t<li><code>1 &lt;= nums[i] &lt;= 100</code></li>\n",
    "</ul>\n"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Description: [number-of-single-divisor-triplets](https://leetcode.cn/problems/number-of-single-divisor-triplets/description/)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Solutions: [number-of-single-divisor-triplets](https://leetcode.cn/problems/number-of-single-divisor-triplets/solutions/)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "test_cases = ['[4,6,7,3,2]', '[1,2,2]', '[1,1,1]']"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "import math\n",
    "from typing import List\n",
    "from collections import defaultdict\n",
    "from itertools import permutations, combinations\n",
    "\n",
    "class Solution:\n",
    "    def singleDivisorTriplet(self, nums: List[int]) -> int:\n",
    "        \"\"\"\n",
    "\n",
    "        :param nums:\n",
    "        :return:\n",
    "        \"\"\"\n",
    "        m1 = defaultdict(int)\n",
    "        for i in nums:\n",
    "            m1[i] += 1\n",
    "        cnt = 0\n",
    "        for i in permutations(m1.keys(), 3):\n",
    "            ans = sum(i)\n",
    "            ok = False\n",
    "            if ans % i[0] == 0 and ans % i[1] != 0 and ans % i[2] != 0:\n",
    "                ok = True\n",
    "            elif ans % i[0] != 0 and ans % i[1] == 0 and ans % i[2] != 0:\n",
    "                ok = True\n",
    "            elif ans % i[0] != 0 and ans % i[1] != 0 and ans % i[2] == 0:\n",
    "                ok = True\n",
    "            if ok:\n",
    "                res = m1[i[0]] * m1[i[1]] * m1[i[2]]\n",
    "                cnt += res\n",
    "        for i in permutations(m1.keys(), 2):\n",
    "            ans = 2 * i[0] + i[1]\n",
    "            ok = False\n",
    "            if m1[i[0]] < 2:\n",
    "                continue\n",
    "\n",
    "            elif ans % i[0] != 0 and ans % i[1] == 0:\n",
    "                ok = True\n",
    "            if ok:\n",
    "                cnt1 = m1[i[1]] * (m1[i[0]] * (m1[i[0]]-1)//2)\n",
    "                cnt += cnt1 * 6\n",
    "        return cnt\n",
    "\n",
    "\n",
    "a = Solution()\n",
    "print(a.singleDivisorTriplet( [9,98,69,99,17,17,85,61] ))\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "from typing import List\n",
    "from collections import Counter\n",
    "from itertools import product\n",
    "\n",
    "class Solution:\n",
    "   def singleDivisorTriplet(self, nums: List[int]) -> int:\n",
    "       counter = Counter(nums)\n",
    "       res = 0\n",
    "       for n1, n2, n3 in product(counter.keys(), repeat=3):\n",
    "           if not n1 <= n2 <= n3:\n",
    "               continue\n",
    "           sum_ = n1 + n2 + n3\n",
    "           if sum(sum_ % n == 0 for n in (n1, n2, n3)) == 1:\n",
    "               good1 = next((n for n in (n1, n2, n3) if sum_ % n == 0))\n",
    "               bad1, bad2 = (n for n in (n1, n2, n3) if sum_ % n != 0)\n",
    "               if bad1 == bad2:\n",
    "                   res += counter[good1] * counter[bad1] * (counter[bad1] - 1) * 3\n",
    "               else:\n",
    "                   res += counter[good1] * counter[bad1] * counter[bad2] * 6\n",
    "\n",
    "       return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def singleDivisorTriplet(self, nums: List[int]) -> int:\n",
    "        cnt=Counter(nums)\n",
    "        ans = 0\n",
    "        lar = max(nums)\n",
    "        for i in range(1,lar + 1):\n",
    "            for j in range(i,lar + 1):\n",
    "                for k in range(j,lar + 1):\n",
    "                    if i == j == k:\n",
    "                        continue\n",
    "                    cur = i + j + k\n",
    "                    flag = (cur % i == 0) + (cur % j == 0) + (cur % k == 0)\n",
    "                    if flag == 1:\n",
    "                        if cur % i == 0:\n",
    "                            if j == k and cnt[j] >= 2:\n",
    "                                ans += cnt[i] * cnt[j] * (cnt[j] - 1) * 3\n",
    "                            elif j != k:\n",
    "                                ans += cnt[i] * cnt[j] * cnt[k] * 6\n",
    "                        elif cur % j == 0:\n",
    "                            if i == k and cnt[i] >= 2:\n",
    "                                ans += cnt[j] * cnt[i] * (cnt[i] - 1) * 3\n",
    "                            elif i != k:\n",
    "                                ans += cnt[i] * cnt[j] * cnt[k] * 6\n",
    "                        else:\n",
    "                            if i == j and cnt[i] >= 2:\n",
    "                                ans += cnt[k] * cnt[j] * (cnt[j] - 1) * 3\n",
    "                            elif i != j:\n",
    "                                ans += cnt[i] * cnt[j] * cnt[k] * 6\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "\n",
    "\n",
    "# # 枚举答案+验证\n",
    "from collections import Counter\n",
    "from itertools import product\n",
    "\n",
    "class Solution:\n",
    "   def singleDivisorTriplet(self, nums: List[int]) -> int:\n",
    "       counter = Counter(nums)\n",
    "       res = 0\n",
    "\n",
    "       # product('ABCD', 'xy') --> Ax Ay Bx By Cx Cy Dx Dy\n",
    "       # product(range(2), repeat=3) --> 000 001 010 011 100 101 110 111\n",
    "       for n1, n2, n3 in product(counter.keys(), repeat=3):\n",
    "           if not n1 <= n2 <= n3:\n",
    "               continue\n",
    "\n",
    "           sum_ = n1 + n2 + n3\n",
    "           if sum(sum_ % n == 0 for n in (n1, n2, n3)) == 1:\n",
    "               good1 = next((n for n in (n1, n2, n3) if sum_ % n == 0))\n",
    "               bad1, bad2 = (n for n in (n1, n2, n3) if sum_ % n != 0)\n",
    "               if bad1 == bad2:\n",
    "                   res += counter[good1] * counter[bad1] * (counter[bad1] - 1) * 3\n",
    "               else:\n",
    "                   res += counter[good1] * counter[bad1] * counter[bad2] * 6\n",
    "\n",
    "       return res\n",
    "\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def singleDivisorTriplet(self, nums: List[int]) -> int:\n",
    "        cnt = [0 for _ in range(max(nums) + 1)]\n",
    "        for c in nums:\n",
    "            cnt[c] += 1\n",
    "        \n",
    "        ans = 0\n",
    "        lar = max(nums)\n",
    "        for i in range(1,lar + 1):\n",
    "            for j in range(i,lar + 1):\n",
    "                for k in range(j,lar + 1):\n",
    "                    if i == j == k:\n",
    "                        continue\n",
    "                    cur = i + j + k\n",
    "                    \n",
    "                    flag = (cur % i == 0) + (cur % j == 0) + (cur % k == 0)\n",
    "                    if flag == 1:\n",
    "                        if cur % i == 0:\n",
    "                            if j == k and cnt[j] >= 2:\n",
    "                                ans += cnt[i] * cnt[j] * (cnt[j] - 1) * 3\n",
    "                            elif j != k:\n",
    "                                ans += cnt[i] * cnt[j] * cnt[k] * 6\n",
    "                        elif cur % j == 0:\n",
    "                            if i == k and cnt[i] >= 2:\n",
    "                                ans += cnt[j] * cnt[i] * (cnt[i] - 1) * 3\n",
    "                            elif i != k:\n",
    "                                ans += cnt[i] * cnt[j] * cnt[k] * 6\n",
    "                        else:\n",
    "                            if i == j and cnt[i] >= 2:\n",
    "                                ans += cnt[k] * cnt[j] * (cnt[j] - 1) * 3\n",
    "                            elif i != j:\n",
    "                                ans += cnt[i] * cnt[j] * cnt[k] * 6\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "g = defaultdict(list)\n",
    "for i in range(1,101):\n",
    "    for j in range(1,101):\n",
    "        for k in range(j,101):\n",
    "            if (i+j+k)%i==0 and (i+j+k)%j!=0 and (i+j+k)%k!=0:\n",
    "                g[i].append((j,k))\n",
    "class Solution:\n",
    "    def singleDivisorTriplet(self, nums: List[int]) -> int:\n",
    "        res=0\n",
    "        cnt=Counter(nums)\n",
    "        for a in set(nums):\n",
    "            for b,c in g[a]:\n",
    "                if b != c:\n",
    "                    res += cnt[a]*cnt[b]*cnt[c]*6\n",
    "                else:\n",
    "                    res += cnt[a]*comb(cnt[b],2)*6\n",
    "        return res"
   ]
  }
 ],
 "metadata": {},
 "nbformat": 4,
 "nbformat_minor": 2
}
